package com.mango.algorithm.tree.binary;

import com.mango.data.structure.binarytree.linknode.TreeNode;

/**
 * 验证二叉搜索树
 * 节点的左子树只包含 小于 当前节点的数。
 * 节点的右子树只包含 大于 当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树。
 * @Author: mango
 * @Date: 2022/4/11 11:07 下午
 */
public class BSTTree {
    public boolean isValidBST(TreeNode root) {
        return isBST(root).isBST;
    }

    public BSTInfo isBST(TreeNode node){
        if(node == null){
            return null;
        }
        BSTInfo left = isBST(node.left);
        BSTInfo right = isBST(node.right);
        int min = node.val;
        int max = node.val;
        // 找到左树和右树里的最大值和最小值
        if(left != null){
            min = Math.min(min,left.min);
            max = Math.max(max,left.max);
        }

        if(right != null){
            min = Math.min(min,right.min);
            max = Math.max(max,right.max);
        }
        // 默认为true,找到不是bst的情况设置为false
        boolean isBST = true;
        // 左树不空，左树不是bst或者左树最大值大于等于节点的值
        if(left != null && (!left.isBST || left.max >= node.val)){
            isBST = false;
        }
        // 右树不空，右树不是bst或者右树最小值小于等于节点的值
        if(right != null && (!right.isBST || right.min <= node.val)){
            isBST = false;
        }

        return new BSTInfo(isBST,min,max);

    }

}
// 收集信息
class BSTInfo{
    public boolean isBST;
    public int min;
    public int max;

    public BSTInfo(boolean isBST, int min,int max) {
        this.isBST = isBST;
        this.min = min;
        this.max = max;
    }
}
